U.S. patent application Ser. No. 888,733 entitled "Architecture For A Storage Access System For High Performance Computer System" discloses a database system architecture intended to support very high levels of query throughput, a powerful query language, rapid execution of complex queries, and full control of concurrently executing queries to preserve database consistency in the face of updates. The above-identified patent application was filed for E. J. Gaussman, K. S. Grewal, and G. E. Herman on July 21, 1986 is assigned to the assignee hereof and is incorporated herein by reference.
The strategy in the architecture is to broadcast the contents of a database repetitively over a high speed transmission medium to a multitude of "listening processors" that observe the database in the form of a high speed bit stream. Data filters may be used to extract information relevant to queries pending locally at the "listening processors".
Illustratively, the database is divided into records and queries are typically directed to identifying particular records. Each record typically comprises a number of attributes. An example of a pending query might be to find a phone number from a database whose records comprise individuals and their phone numbers. Another example of a query might be to count the number of individuals earning over fifty thousand dollars per year in a database whose records comprise employment information.
Desirably, each "listening processor" or record access manager includes a plurality of data filters. A data filter may be defined as a device which interfaces a conventional relatively low speed processor with a high speed data stream in order to obtain certain data from the high bit rate data stream in response to instructions from the conventional low speed processor. Such data filters play a particularly important role in the database architecture described above because they are the devices which actually execute the locally pending queries. The architecture operates most efficiently when high speed, highly efficient data filters are used to extract desired information from the cyclically broadcast high speed data stream.
Currently available data filters are generally not fast enough to make a database architecture in which database contents are cyclically broadcast commercially viable. Many presently available data filters use multiple comparator arrays which exhibit significant amounts of redundancy in hardware resources. Examples of such data filters may be found in Kung, H. T. and Lehman, P. L., "Systolic (VLSI) Array for Relational Database Operations," Proceedings of ACM-SIGMOD 1980, May 1980; Curry, T. and Mukhopadhyay, A, "Realization of Efficient Non-Numeric Operations Through VLSI", Proceedings of VLSI '83, 1983; Ozkarahan, E., Database Machines and Database Management, Englewood Cliffs, N.J., Prentice/Hall, 1986; Takahashi, K., Yamada, H., and Hirata, M., "Intelligent String Search Processor to Accelerate Text Information Retrieval", Proceedings of Fifth Int'l Workshop on Database Machines, pp 440-453, Oct., 1987. The data filters described in these references have either low utilization of comparator resources or utilize significant amounts of redundant comparisons on attributes that are not of interest. Such data filters based on comparator arrays are also limited due to the lack of parallelism resulting from the processing of data one byte at a time.
Another prior art approach to data filtering involves the use of a general purpose processor and external buffer management techniques (see e.g. Ozkarahan, E., "Database Machine and Database Management, pp. 236-255, Englewood Cliffs, N.J, Prentice Hall, Inc., 1986). While general purpose processors can take advantage of comparing multiple bytes at a time, they suffer performance degradation when used in data filter applications involving the repetitive execution of the same instructions with respect to each record in a database in the form of a high speed data stream. One reason for the performance degradation is the need for repetitive off-chip instruction and attribute fetch. Another reason for the degradation is that the instruction sets utilized by general purpose processors are not designed for query applications wherein the same group of instructions is repetitively executed.
The instruction set of a general purpose processor usually includes branching instructions. This means that the instructions provided to the processor are not necessarily executed in sequence. Accordingly, pipeline processing is not used most efficiently in such processors. Any time processing branches to an instruction that is not next in sequence, the entire pipeline must be flushed. Thus, in data filter applications requiring execution of the same group of instructions for each record in a database bit stream in order to identify a small subset of records, large numbers of pipeline flushes can be expected. Such pipeline flushes significantly reduce performance.
In view of the above, it is an object of the present invention to provide a high speed data filter for performing relational and simple numeric operations on a high speed data bit stream.
It is a further object of the present invention to provide a data filter for carrying out queries in a database system architecture wherein a database comprising a sequence of records is cyclically broadcast over a high speed downstream transmission medium.
It is a further object of the invention to provide a data filter in the form of a processor having a unique architecture and a unique instruction set especially adapted for carrying out query operations on a high speed bit stream, which data filter overcomes the shortcomings of the prior art data filters and general purpose processors described above.